#include<bits/stdc++.h>
using namespace std;
const int N = 1.5e5+10;
int n;
bool beg;
int a[N];
int lst[N];
int pre[N],nxt[N];
struct segment_tree1{
    int ls[N*290],rs[N*290],ma[N*290];
    int pcnt;
    void update(int &now,int cop,int l,int r,int p,int v){
        now = ++pcnt;
        ls[now] = ls[cop];
        rs[now] = rs[cop];
        ma[now] = max(ma[cop],v);
        if(l == r){
            return;
        }
        int mid = (l+ r)/2;
        if(p <= mid){
            update(ls[now],ls[cop],l,mid,p,v);
        }else{
            update(rs[now],rs[cop],mid+1,r,p,v);
        }
    }
    int qma(int now,int l,int r,int x,int y){
        if(x <= l && r <= y){
            return ma[now];
        }
        int mid = (l + r)/2;
        int ma = 0;
        if(x <= mid){
            ma = max(ma,qma(ls[now],l,mid,x,y));
        }
        if(mid < y){
            ma = max(ma,qma(rs[now],mid+1,r,x,y));
        }
        return ma;
    }
}sg1;
struct segment_tree2{
    vector<int> pres[N<<2];
    vector<int> rots[N<<2];
    void build(int now,int l,int r){
        vector<int> idx;
        for(int i = l;i <= r;i++){
            idx.push_back(i);
        }
        sort(idx.begin(),idx.end(),[](int a,int b){
            return pre[a] < pre[b];
        });
        for(int i = 0;i < idx.size();i++){
            if(!pres[now].size()){
                pres[now].push_back(pre[idx[i]]);
                rots[now].push_back(0);
            }else if(pres[now].back() != pre[idx[i]]){
                pres[now].push_back(pre[idx[i]]);
                rots[now].push_back(rots[now].back());
            }
            int nr;
            sg1.update(nr,rots[now].back(),1,n + 1,nxt[idx[i]],a[idx[i]]);
            rots[now][rots[now].size() - 1] = nr;
        }
        if(l == r){
            return;
        }
        int mid = (l + r)/2;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
    }
    int query(int now,int l,int r,int x,int y){
        if(x <= l && r <= y){
            int p = lower_bound(pres[now].begin(),pres[now].end(),x) - pres[now].begin();
            if(!p){
                return 0;
            }else{
                p--;
                return sg1.qma(rots[now][p],1,n + 1,y + 1,n + 1);
            }
        }
        int mid =(l + r)/2;
        int ma = 0;
        if(x <= mid){
            ma = max(ma,query(now<<1,l,mid,x,y));
        }
        if(mid < y){
            ma = max(ma,query(now<<1|1,mid+1,r,x,y));
        }
        return ma;
    }
}sg;
bool ed;
int main(){
    //cerr<<(&ed - &beg)/1048676.0<<'\n';
    int m;
    int ma = 0;
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        pre[i] = lst[a[i]];
        lst[a[i]] = i;
        ma = max(ma,a[i]);
    }
    for(int i = 1;i<=ma;i++){
        lst[i] = n + 1;
    }
    for(int i = n;i >= 1;i--){
        nxt[i] = lst[a[i]];
        lst[a[i]] = i;
    }
    sg.build(1,1,n);
    int lastans = 0;
    for(int i = 1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        x = (x + lastans)%n + 1;
        y = (y + lastans)%n + 1;
        if(y < x){
            swap(x,y);
        }
        lastans = sg.query(1,1,n,x,y);
        //cerr<<x<<' '<<y<<' ';
        cout<<lastans<<'\n';
    }
}